/*
 * (C) 2012	Sheng Yi
 * KMP --- a elegant string match algorithm
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void next(char* pattern, int prefix[], int len);
int match(char* text, char* pattern);

int main()
{
	int i, len;
	char text[100];
	//char* pattern = "agacagata";
	char pattern[100];
	int prefix[100] = {0};
	printf("Please input the pattern string: ");
	scanf("%s", pattern);
	printf("Please input the text string: ");
	scanf("%s", text);
	len = strlen(pattern);
	next(pattern, prefix, len);
	for (i = 0; i < len; i++)
		printf("%d ", prefix[i]);
	printf("\n");
	i = match(text, pattern);
	printf("The first position of '%s' in '%s' is : %d\n", pattern, text, i);
	return 0;
}

/*
 * Get the prefix array of pattern string
 */
void next(char* pattern, int prefix[], int len)
{
	int i, j;
	prefix[0] = 0;
	for (i = 1; i < len; i++)
	{
		j = i;
		while (j > 0)
		{
			if (pattern[i] == pattern[prefix[j - 1]])
			{
				prefix[i] = prefix[j - 1] + 1;
				break;
			}
			else // This branch is a bit more complicated
			     // just one statement ^_^
				j = prefix[j - 1];
		}
		if (j == 0)	// no prefix
			prefix[i] = 0;			
	}	
}

/*
 * Find the first position that when pattern appears in text
 */
int match(char* text, char* pattern)
{
	int i, pos;
	int len = strlen(pattern);
	int text_len = strlen(text);
	int* prefix = (int*)malloc(sizeof(int) * len);
	next(pattern, prefix, len);
	pos = 0;
	for (i = 0; i < text_len; i++)
	{
		while (pos > 0 && pattern[pos] != text[i])
			pos = prefix[pos - 1];

		if (pattern[pos] == text[i])
			pos++;
		if (pos == len)
			break;
	}

	// don't forget free the memory, becarefull memory leak!!
	free(prefix);

	if (i < text_len) //found
		return i - len + 1;
	else	// text_len == i, not found
		return -1;
}
